package com.javabasic.algorithm.leetcode;

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see     [162. 寻找峰值 - 力扣（LeetCode）](https://leetcode.cn/problems/find-peak-element/description/?envType=daily-question&envId=2023-12-18)
 * @since Created by work on 2023/12/18 21:28
 */
public class FindPeakElement {


    public static Stream<int[]> testData() {
        return Stream.of(
                new int[]{1, 2, 3, 1},
                new int[]{1,2,1,3,5,6,4}
        );
    }

    @ParameterizedTest
    @MethodSource("testData")
    public void findPeakElementTest(int[] nums) {
        System.out.println(findPeakElement(nums));
    }

    /**
     * 根据题目条件，一个数的左边比它大，那么它的左边一定存在一个峰值，右边同理
     *
     * 二分找到一个值mid如果是峰值就退出
     * 如果不是峰值
     * 那左右两边肯定有一个比它大的
     * 左边那个比它大，那么左边那个数有可能是最大值，作为峰值，去跟他
     * 右边那个数大，右边那个数有可能是峰值，去右边找
     * 一次类推，总能找到峰值
     *
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        int len = nums.length;
        if (len == 1 || nums[0] > nums[1]) {
            return 0;
        }
        if (nums[len - 1] > nums[len - 2]) {
            return len - 1;
        }

        int left = 0;
        int right = len - 1;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            // 边界特判,防止数组越界
            if (mid == 0) {
                return nums[0] > nums[1] ? 0 : 1;
            } else if (mid == len - 1) {
                return nums[mid] > nums[mid - 1] ? mid : mid-1;
            }

            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            }

            if (nums[mid - 1] > nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}
